/**
 * Definition for singly-linked list.
 * **/
   class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class Solution {
    public void reorderList(ListNode head) {
        //排除只有一个节点或者空链表
        if(head == null || head.next == null || head.next.next == null){
            return;
        }
        //先确定链表的长度
        ListNode cur = head;
        int count = 1;
        while(cur.next != null){
            count ++;
            cur = cur.next;
        }
        //找到链表的中间节点
        cur = head;
        for(int i = 1;i < count / 2 + 1; i++){
            cur = cur.next;
        }
        //将后半段链表存入数组
        ListNode[] arr = new ListNode[count / 2 + 1];
        for(int i = 0;i < arr.length;i ++){
            arr[i] = cur;
            if(cur.next != null){
                cur = cur.next;
            }else{
                break;
            }
        }
        //将前半段链表存入数组
        ListNode[] arrRight = new ListNode[count / 2];

        //开始重新连接链表
        ListNode pos = head;
        for(int i = arr.length - 1;i >= 0;i --){
            ListNode node = pos;
            if(node.next != null){
                arr[i].next = node.next;
                arr[i].next.next = null;
            }else{
                arr[i].next = arr[i - 1];
                break;
            }
            pos.next = arr[i];
            pos = node.next;
        }
    }
}